For any suggestions or feedback regarding these notes,

please contact Pragy Agarwal

Relational (SQL) Databases

Structured Query Language (SQL)

Its a "query" language - a way of specifying what to fetch from the DB.

SQL is not a DB type - it's just a query language.

SQL is the de-factor query language for Relational DBs.

When people say SQL, they mean Relational DB.

Even in Relational DBs, you can choose other querying languages - example: GraphQL.

Common Relational Database implementations: MySQL, PostgreSQL, OracleDB, MSSQL, SQLite, IBM DB2, Amazon RDS, ..

Strengths of RDBMS

All these strengths apply at low scale

Low Scale: "queries/second, amount of data" is small enough to be handled by a single server.

Data is stored in tables - tables can have relations with each other (via foreign keys).

Normalization

It is recommended to model data in a normalized manner.

Normalization prevents anomalies & reduces redundancy.

Strong Schema

Well Defined

1. You know exactly what tables exist
2. You know exactly what columns exist in each table
3. You know exactly the data-type of each column

1. Allows you to allocate fixed amount of space for each row on the disk

Static

1. The schema does not change for different rows.
2. Changing the schema is not encouraged, and is difficult.

1. It is possible to add/remove columns from an existing table — however that requires a complete table re-write

1. extremely slow (table migration)
2. requires the service to be down

1. they're ways around this (rolling migration)

Enforced

If a row violates the table's schema, then the DB will let you know. It won't let the write succeed.

ACID Transactions

Extremely powerful & good to have.

Atomicity

All or nothing: Each transaction is either executed completely (all rows) or not at all. There are no partial states.

Imagine that Khushboo is transferring 1 million $ to Vishudh.

1. Check if Khushboo has sufficient account balance
2. Deduct 1 million $ from Khushboo’s account
3. Add 1 million $ to Nimish’s account

It should not be the case that the money gets deducted from Khushboo, but isn’t credited to Nimish. We want to ensure that either the money is not deducted from Khushboo, or, if deducted, it must be successfully credited to Nimish.

Consistency

ACID consistency =/= CAP consistency  (wait, what !!?)

CAP Consistency: no stale reads — when we have multiple copies of the data (replicas/cache), and some copy is out-of-sync with other copies, then we should not read from the stale copy.

ACID Consistency: db constraints are enforced

1. schema: columns & data-types
2. not-null / unique / foreign key constraints

• you can have custom constraints as well (for example, the value in this column should only be a lowercase string)

3. triggers
4. every transaction should leave the database in a consistent state

Isolation

Multiple transactions that are running simultaneously don't mess with each other.

There's different isolation levels. (homework: read up on this)

Transaction 1: Khushboo– 1 million $ → Vishudh

1. balance = get_balance(Khushboo)
2. assert balance > 1 million $
3. new_balance = balance - 1 million $
4. set_balance(Khushboo, new_balance)
5. receiver_balance = get_balance(Vishudh)
6. set_balance(Vishudh, receiver_balance + 1 million $)

Transaction 2: Khushboo – 1 million $ → Nandani

1. balance = get_balance(Khushboo)
2. assert balance > 1 million $
3. new_balance = balance - 1 million $
4. set_balance(Khushboo, new_balance)
5. receiver_balance = get_balance(Nandani)
6. set_balance(Nandani, receiver_balance + 1 million $)

Khushboo started with 1 million $

T1: S 1..3

T2: S 1..3

T1: S 4       Khushboo’s new balance = 0

T2: S 4       Khushboo’s new balance = 0

T1: S 5..6

T2: S 5..6

This is lack of isolation! This should NOT happen.

Durability

Any transaction that has been executed will be stored in non-volatile storage (HDD/SSD) and not just the volatile RAM.

Note: Durability does NOT protect you against HDD failures - only replication does.

Other Strengths

1. Very powerful querying capabilities

• you can perform joins
• filtering by column values
• aggregate calculations
• grouping
• nested queries
• recursive queries (CTEs)

2. Extra features

• Full text search
• Geospatial queries
• JSON
• …
• they offer pretty much every feature that any other database in the world provides! (just at low scale)

3. Relational DBs are extremely mature

• Relational database theory predates modern computer hardware!
• battle tested across thousands of various scenarios, by millions of companies!

Weaknesses of RDBMS

When the scale becomes large, all the strengths become weaknesses!

Large Scale: data or req/s is too large to fit on a single server

Normalization

On the frontend, we (almost) always need to show “denormalized” data (data about a lot of entities)

Therefore, to display the data, we need to perform joins.

For example, to display the page (https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array) you will need to join around 30-40 tables

1. If you have lots of tables, then joining all of them grinds to a halt
2. What if the data is too large to fit on a single server

1. joins have to be executed across servers!

• impossibly slow
• too much n/w overhead

Strong Schema

What if the data itself is inherently unstructured?

Q: How to model product listings for Amazon in a SQL DB?

Amazon has 10 million+ products across 10,000+ categories.

Every category has a different attribute set

1. T-shirts: Brand, Price, Color, Fabric, Neck-shape, Sleeve length
2. Laptops: Brand, Price, Screen Size, RAM, CPU, GPU, OS
3. Notebook: Brand, Price, Page thickness, Number of Pages, Ruled

Giant table with All Columns

products: id, name, brand, price, Color, Fabric, Neck-shape, Sleeve length, Screen Size, RAM, CPU, GPU, OS, Page thickness, Number of Pages, Ruled, ...

Too many columns (10,000 categories, 10 unique cols per category ⇒ 100,000 columns)

• every row will only store data for 10 columns - rest of the 100,000 columns will be nulls

• null in itself is bad — because it is ambiguous
• null can mean two things

• missing data: the data is there, but we just don’t know it
• undefined value: what’s the Page-Thickness of this t-shirt?

• SQL pre-allocates space for the entire row (all columns included)

• even for the columns where the value is null

• you're effectively wasting 99.99% of the disk space

Multiple tables

products: id, name, brand, price

tshirts: product_id, Color, Fabric, Neck-shape, Sleeve length

laptops: product_id, Screen Size, RAM, CPU, GPU, OS

notebooks: product_id, Page thickness, Number of Pages, Ruled

… 10,000 such tables, one for each product type

1. if you want to fetch data like "find top 10 most expensive products, which are of color red" then you will have to join across 10,000 tables.
2. SQL is not designed for this scale

1. SQL can handle lots of rows and terabytes of data (few tables, lots of data in those tables)
2. but SQL cannot handle lots of "schema" (many tables)

Attribute List

products: id, name, brand, price

product_attributes: product_id, attribute_name, attribute_value

1. Schema enforcement is lost: laptops can now have fabric

1. you can still enforce attributes on the application layer

1. that breaks separation of concerns.
2. now your data validation lives partially in DB layer and partially in App server layer

2. but the DB has lost the ability to enforce a schema (you can assign any attribute to any entity)

2. Fetching data about a single entry is too expensive: if you need to show the details of the laptop - you have to fetch all attributes of the laptop, and then join them into an array

So we see that since the data was inherently "semi-structured" SQL was not a good choice.

At low scale (only 2-3 different product categories) SQL could've worked.

Q: But modern SQL databases support JSON. So can’t I just use that?

Yes, and no!

Relational DBs like Postgres, MySQL have 1st class support for JSON. However, it still is not designed to handle scale.

ACID Transactions

When the data is large (high scale), then you need sharding - because you can't store all the data in a single server.

Sharding nullifies ACID

SQL dbs provide ACID guarantees only within a single server.

Because it is easy to do that

1. inside a single server, you can acquire locks easily (OS, hardware facilitates locks/semaphores)
2. inside a single server, you can share memory (RAM, HDD) - so no n/w overhead to communicate across multiple transactions - no consistency (stale read) issues when two threads are reading the data from the same location in the RAM
3. inside a single server, you know whether the write has succeeded or failed
4. inside a single server, writes mostly always succeed

If you've multiple servers

1. distributed locks is extremely hard & extremely slow (because PACELC theorem) - 2PC / Zookeeper
2. sharing memory is not possible - keep copies, and that leads to consistency challenges
3. don't know if the writes succeeded - you have to pass acknowledgements
4. networks & servers regularly fail

Providing ACID guarantees across shards is extremely difficult

1. possible
2. but, very slow, and very complex!

NoSQL Databases

What is NoSQL?

NoSQL =/= No SQL (what??)

No SQL =/= don't use SQL

NoSQL = Not Only SQL - we will still continue using relational databases, but, we will augment their capabilities with additional non-relational databases

SQL dbs have existed for a very long time - even before modern computers came into picture, the theoretical foundations for relational algebra were already laid.

NoSQL dbs are extremely recent

1. first NoSQL db was BigTable by Google
2. NoSQL dbs started getting popular only after 2005

1. most internet giants did not even exist before 2005

3. Around 2009/2010 there was a conference about non-relational DBs. The promoters needed a twitter hashtag to go viral - #NoSQL

Don't jump to NoSQL

Your de-facto choice should ALWAYS be Relational (SQL) databases.

You can use NoSQL - but, only if, you can justify the need for it.

Modern SQL databases (like postgres, mysql) can do absolutely everything that any NoSQL can do & even more

• just at a low scale

• the bar of "low scale" keeps increasing every day

• for up to 1 million userbase, a SQL db will just work flawlessly
• 99% of the companies use SQL databases, and 99% of companies do NOT need NoSQL databases primarily!

SQL

1. ACID
2. Normalization
3. Do everything, decently well (Jack of all trades)
4. 1 server

NoSQL

1. BaSE
2. Denormalized data & redundancy
3. Do 1 thing, extremely well        (Master of one)
4. Multiple servers (built in sharding, auto scaling, load balancing, ..)

BaSE

https://aws.amazon.com/compare/the-difference-between-acid-and-base-database/

Basically Available

The system as a whole will remain available, even though some services might be unavailable for a small fraction of the users for some time.

High availability (for the entire system, not for individual services/users)

Soft State

ACID transactions provide atomicity (all or nothing)

Soft state: Transactions can be in a partial state for some time (even for extended time – weeks!) - they're not all or nothing — but eventually, the data will become consistent and atomic.

(we will see this in the last class of HLD - distributed transactions in microservices - Saga Pattern)

Eventually Consistent

There might be stale reads. But, eventually (if we wait long enough) every write will be reflected across the entire system (all replicas)

Horizontally Scalable

SQL databases require manual sharding - they don't provide built-in support for sharding

(note: most modern SQL dbs have built-in support for replication, but not sharding)

Note: you can shard a SQL database either

• by using a 3rd party extension
• by doing it manually (writing LB code, managing the server state..)
• by using a “managed” cloud service like Amazon RDS

NoSQL db are automatically sharded - they're built with horizontal scaling in mind.

You just have to get a bunch of servers, and install the database on them - and they will figure stuff out themselves (LB, autoscaling, sharding, data distribution, replication, fault tolerance..)

Denormalization & Replication

SQL databases discourage denormalization & redundancy to remove anomalies.

NoSQL databases realise that

1. in the frontend you're anyway going to show denormalized data
2. to prevent data loss, we're going to have multiple copies of the data anyway

NoSQL dbs encourage storing data in a denormalized manner / semi-structured (sometimes even schemaless) manner.

Weaknesses of NoSQL databases

SQL databases have tons of features

1. joins
2. powerful ways to structure data
3. enforceable constraints
4. triggers
5. ACID guarantees
6. powerful indexing
7. powerful filtering
8. recursive queries
9. modern features

1. full text search
2. semi-structured data (first class json support)
3. spatial indexing (nearest neighbor queries)
4. vector support (KNN queries)
5. denormalized views (table views)

Any feature that you can think of, modern SQL dbs have it.

The only con of SQL is that it is feasible only at low scale.

SQL databases "generalize" - jack of all trades, master of none (they don’t work at scale)

NoSQL databases can work at massive scale because they don't support most of the features

1. it is hard to do everything perfectly
2. it is easy to do a few things flawlessly

NoSQL databases "specialize", jack of 1 trade, and master of it

Choosing a Sharding Key

Sharding key decides how your data gets distributed across various db servers.

It will also determine how the queries need to be routed to fetch the data.

Primary Key vs Sharding Key

Primary Key: Uniquely identifies a item in the data (e.g. row in a table) — what you’re talking about

Q: Does a Primary key have to be unique across tables?

No.

It is totally okay for there to be a user_id = 1 and a product_id = 1

Both can have the value 1, because we are querying different tables – we’re talking about different entities.

Q: Does a Primary key have to be unique across shards, for the same table?

Yes! Primary key should be unique for each row within a table, irrespective of whether the table is on a single server, or whether the table is sharded.

The following is wrong

Shard 1 has user_id = 1 name = Sai

Shard 2 has user_id = 1 name = Abhishek

Sharding Key: Just tells you how to distribute the data: what data goes to what server —- where to find the data

users (id, name, gender)

A, Akshay, Male

B, Balaji, Male

C, Chandani, Female

for user table, the PK = id, and SK = id

user_posts (id, user_id, title, content)

1, A, Hi, Hello World

2, A, Bye, Going to sleep

3, B, Wassup, What’s everyone doing

4, C, Context?, Who are you guys? Why are you in my home?

for user_posts table, the PK = id, SK = user_id

user_friendship (id, user_id, friend_id, affinity)

1, A, B, 100%

2, B, A, 100%

3, A, C, 50%

4, C, A, 50%

for user_friendship table, the PK = id, SK = user_id

Suppose we’re sharding by the user_id, then all tables must have user_id

Shard 1:

users (id, name, gender)

A, Akshay, Male

user_posts (id, user_id, title, content)

1, A, Hi, Hello World

2, A, Bye, Going to sleep

user_friendship (id, user_id, friend_id, affinity)

1, A, B, 100%

3, A, C, 50%

Shard 2:

users (id, name, gender)

B, Balaji, Male

user_posts (id, user_id, title, content)

3, B, Wassup, What’s everyone doing

user_friendship (id, user_id, friend_id, affinity)

2, B, A, 100%

Shard 3:

users (id, name, gender)

C, Chandani, Female

user_posts (id, user_id, title, content)

4, C, Context?, Who are you guys? Why are you in my home?

user_friendship (id, user_id, friend_id, affinity)

4, C, A, 50%

Q: Does the Sharding key have to be unique across tables?

No. This question is weird, because all the tables are sharded in the same way.

Q: Does the Sharding key have to be unique across shards?

Yes. Because if it was same, then we wouldn’t route to different shards.

Q: Which should we use? Primary Key or Sharding Key?

Both!

Both of these keys will coexist.

It is common to use the same column as both the primary & sharding key

for example, we can use user_id as primary key for users table, and also shard the db by user_id

but not always. It is totally possible to have a different primary key and different sharding key

for the posts table, the primary key is post_id

If you want to read/write some data, which key should you use?

You need to use both!

Sharding key will tell you which server to go to (routing).

Primary key will tell you which entry to touch inside that server.

It is possible to omit the Sharding Key. Just the PK is enough to uniquely identify a row. However, if the Sharding key is not used, then our query will be a fan-out query (we will have to hit all shards)

Suppose you’re going to school to find your little sister.

Primary Key: Your sister’s name & her student id

Sharding Key: The class number

To find your sister, you MUST know the primary key.

If you also know the Sharding key, then your search will be faster, because you will exactly which classroom (server) to go to.

If you don’t know the sharding key, then you will have to fan-out and search through all classrooms (servers)

Q: Can we have more than 1 sharding key in the same database?

No. The sharding key can be composite (have multiple columns), but, it MUST be the same group of columns across the entire database.

If you need different sharding keys, you need different databases.

If there are multiple tables in the DB, does that mean that ALL these tables must have this sharding key column?

Yes.

If you have some data that doesn’t need to be split, or is required across all shards, in that case, you can either

1. Replicate it across all shards: if a table is very small, you can omit the sharding key, but in that case, this table will be replicated across ALL shards. You MUST make sure that the table doesn’t get modified frequently.
2. You can have a separate database for it

Q: Can a sharding key be composite?

Yes. Totally allowed.

For example, you can choose (class-number, gender) as sharding key, like in a non-co-ed school.

Q: Is it possible to change the sharding key later?

Yes, possible. But, not recommended!

Changing the sharding key would require complete re-shuffling of the data across all the servers — very very expensive, and will most likely require database downtime.

This is why it is very important to choose a good sharding key upfront when you’re the designing the architecture.

Q: What if some row has the sharding key value set to null?

Bad idea.

Still, the LB won’t care. It will just treat “null” as any another value.

So, all rows, which have sharding_key = null will end up in the same shard.

What constitutes a "Good" Sharding Key

Mental Model

Suppose you’re sharding by column “SK”.

Consider 2 rows, R1 and R2.

• If the Sharding key value is same for these two rows R1.SK == R2.SK

• these two rows will end up in the same shard (guaranteed)

• If the Sharding key value is different R1.SK =/= R2.SK

• they will most likely end up in different shards (at least, we should assume so)
• they can end up in the same shard (because 1 shard holds multiple sharding keys based on consistent hashing)

1. Equal data & load distribution across various servers

All key values should be equally likely.

If some values are more likely than others - that will lead to "hot shards" (a shard that is overwhelmed with data/requests)

Age: ages 0-5 are less likely. Ages 50+ are less likely. Ages 15-30 are most likely. There will be no users above the age 100 (very unlikely).

Sharding based on age will be a bad idea, as it will lead to poor load distribution.

Gender: depending on the application, you can have hot shards. Most of the students @ Scaler are male (because there’s gender disparity in higher technical studies)

User id: user is unique for each user. Suppose you want to shard posts by the user id, then of course, there will be some users that have made many many posts and some users that have made 0 posts.

But since each server has 100,000s of users, overall, the data distribution across the servers will be pretty even — the normal users & the influences will get distributed more or less equally across the various servers.

Note: this is not always true: eg, "celebrity problem", especially for notifications systems.

Q: if we're sharding by user_id, does that mean that each user gets a dedicated server? If we have 2 billion users, do we need 2 billion servers?

No. A single server will house multiple users (because multiple values of the key can hash to the same server)

If Post_13 is by User_1 and Post_20 is by User_2, then most likely, these posts will end up in different servers.

2. High Cardinality

Cardinality = count of the set of possible values

Age: {0, 123} has 124 possibilities max.

This means that if we have 125 servers, then 1 server will not get any value.

Basically, we're limited to max 124 servers. We cannot scale any further than that.

Gender: {Male, Female, LGBTQ+} has 3 possibilities max.

This means that if you have 4 servers, then 1 server will be idle.

Max scaling possible is only 3 servers.

Even if you have 1 billion users, you will be forced to somehow fit them into 3 shards.

User_Id: {64 bit value} has 16 quintillion possibilities

There's no limit to the number of servers we can scale to. 10 million servers? No issue.

Note: we're not saying that we will have 16 quintillion servers. A single server will house millions of users.

Cardinality of the sharding key doesn’t define how many servers you have. But it gives you an upper limit on how many servers you can scale to in the future.

3. Part of every read/write request

Because if the sharding key is not part of the request, then how will you route the request in the first place? You will have to go to every shard - fan-out (bad)

Imagine that we’re sharding by gender. We want to load the profile page of Tanisq.

select * from user_profiles

where user_id = [1234]

This query will fan-out, because the DB LB doesn’t know which shard to hit, because it doesn’t know the gender of Tanisq.

select * from user_profiles

where user_id = [1234]

  and gender = ‘MALE’

This query will not fan out. But do you think your app server will make this query?

When the app server is trying to render the profile page, how on earth does it get the value for the gender column?

4. No fan-outs

Most frequent queries should have to hit only 1 (or at most 2) shards.

No frequent query should lead to a fan-out request.

Note: rare queries are okay to fan-out — you cannot optimize every single query

5. Immutable

The value of the sharding key should not change for any row.

Because if we change the value of sharding key, then we will have to re-shuffle the data.

Age: what happens when the user's B'day comes? We will have to move the user to a different server because the age has changed.

Examples

Banking System

• Users can have active bank accounts across cities.
• Most Frequent operations

• Balance Query (user_id, account_id)
• Fetch Transaction History (user_id, account_id, date_range)
• Fetch list of accounts of a user (user_id)
• Create new transactions (sender_id, receiver_id, amount)

• note: sender_id and receiver_id both are composite columns comprising of (user_id, account_id)

location (city_id)

A user can have accounts across multiple cities. If we shard by location, then, we will need to store the user's data across multiple shards.

• If we fetch list of accounts of users, we will have to make a fan-out request.
• Poor load distribution (large cities will have much more data than small cities)
• Not part of request
• low cardinality

branch_id

(same issues as location — branch-id is just more granular)

user_id

ideal sharding key here.

This means that 1 user's data will be housed entirely within a single server (note: 1 server still houses thousands of users)

• balance enquiry: Balance Query (user_id, account_id)
  hit only 1 shard (the user's shard)

• transaction history: hit only 1 shard (all the user's transactions will be there)
• list of accounts of the user: hit only 1 shard
• transaction: this transaction is data about both the sender and the receiver

• each transaction has to be stored in 2 shards (sender's shard + receiver's shard)
• this is NOT a fan-out. Hitting 2 shards is okay.
• this is still difficult, because you will need to do this atomically (2 Phase Commit), it will have high latency and low availability

transaction_id

• Is not even available for any of our queries.
• Transaction id is generated in the response. It's not part of the request query.

Any id/entity that is generated by the system (ticket / booking / transaction) cannot be used as the sharding key.

Q: isn’t the user_id also generate by the system.

Yes, but only once, when the user registers. For any subsequent request made by the user, the user_id is available at the client side, and the client will send this user id along with every request (via cookie or auth-token)

account_balance

• Subject to change. Every time the user adds/removes money, we will have to move their data.
• Not part of the request.
• Poor load distribution.

timestamp

NEVER choose timestamp.

• unequal load distribution (recent days are hot, future days have 0 data)
• subject to change (updated_at timestamp can be changed)
• not part of the request

account_id

account_id is fine for most of our queries, but not for the basic user dashboard.

In the interface, the user might want to see the list of accounts they have.

If we shard by the account_id, then different accounts of the same user might go to different servers.

So the dashboard request for the user will be a fan-out query.

IRCTC (Railway ticket booking service in India)

• Prevent double booking of seats (at least for confirmed, non-RAC tickets)
• Handle peak load during Tatkal window (20x or more than the average load)

book_ticket(user_id, train_id, date_of_journey, class, seat_preference, meal_preference, ...) => ticket: {id, details}

Ticket ID

ticket_id is not part of the request - it is generated in the response

Date of travel

Timestamp - so big no no

Any data for past dates will now be immutable. You cannot book a ticket for a journey that has already happened in the past. You cannot modify (cancel, add lunch services) the ticket if the journey has already completed.

User ID

Users are distributed across the shards.

Let’s suppose that Ashok is trying to book a ticket in Rajdhani

We need to ensure that Ashok doesn't get allotted the same seat.

• Sanjana has booked a ticket in Rajdhani for 15 feb
• Rohit has also booked a ticket in Rajdhani for 15 feb
• Ashok is trying to book a ticket in Rajdhani for 15 feb

If we shard by user_id, then Sanjana’s ticket data is in her shard, Rohit's ticket is in his shard.

To ensure Ashok doesn't get a duplicate seat, we've to hit both Sanjana & Rohit's shards. In fact we need to hit all the shards.

We don't know which users have booked which tickets.

We have to hit all shards to check if a particular seat has been booked or not - fan out.

Train ID

If we shard by train_id, then tickets of 1 train are stored completely within a single shard.

• Sanjana & Rohit are travelling in Rajdhani on 15th feb, so both these tickets will be in the same shard

• note: not the user data, just the ticket data

• Vijay is travelling in Shatabdi on 15th feb

can their seats collide? No, the trains are different!

So when checking for duplicates, we only need to check the tickets for this train - just 1 shard.

IRCTC facilitates ~13k passenger trains ⇒ cardinality is decent

Q: But a single user can also book tickets in multiple trains — how will we store the user data then? Will that be split across servers?

Note that user data can be sharded by user_id   (user dashboard service)

And for booking ticket, the ticket data can be sharded by train_id  (booking microservice)

Each ticket will be stored in 2 database - tickets db (sharded by train_id), and the user's db (sharded by user_id)

Q: Suppose we wish to find all the journeys happening on a given day

That will be a fan-out.

But note that this is NOT a frequent query!

If it were a frequent query, then we would come up with another solution

• another solution doesn't mean that we change the sharding key

• we can't change the sharding key, because train_id is the ideal sharding key for preventing double-booking

• we can have another database that is sharded by date that provides this data to us (IRCTC actually does this!)

Facebook Messenger

• Send & Receive 1-1 messages

• sendMessage(sender_id, recipient_id, message) → Ack/Failure
• viewMessages(user_id, other_person_id) → List of messages

User ID

This means that all messages that are (both) sent and received by Sanjana will be in 1 shard.

If Sanjana wants to view the conversation history b/w herself and Sachin, her requests only have to go to her shard. Her shard will contain all messages she has sent to Sachin and all messages Sachin has sent to her.

Sanjana ⇒ Sachin: this message must be stored in both Sanjana's shard & Sachin's shard. Not a fan-out.

Message ID / Message Digest

It is created in the response - once the message has been sent (it's not part of the request)

What if we generate the message id on the client side? In that case, the message id can be part of the request.

Sharding my message id would mean that the messages will be distributed across servers - any message can go to any server (based on the hash of message id)

If I want to find all messages that Sanjana sent to Sachin - I will have to go to all shards, which is a fan-out

Slack

• Send & Receive messages in groups

• A group can have up to 100,000 participants

• Send & Receive 1-1 messages

User ID

Consider a "Announcements" group that has 100,000 participants.

Sanjana sends "Hi" in that group.

If we shard by user_id, we can design in 2 ways

1. "Hi" will be stored only in Sanjana's (sender) shard.

• When any participant of the group (Tarun) wants to view the conversation in the group - they must hit all shards (because anyone could've sent a message in that group)
• writes: 1 shard
  reads: 100,000 shards

2. "Hi" will be stored in both Sanjana's (sender) shard & the receiver's shard

• there's 100,000 receivers
• so the message has to be written to all those shards.
• writes: 100,000 shards
  reads: 1 shard

Group ID

All messages that are sent & received within any group ("Announcements" for example) will be in a single shard.

Sanjana ⇒ "Hi" ⇒ Announcements

• Write: only 1 shard (the shard where all messages of Announcements group is stored)
• Read: only 1 shard (the shard where all messages of Announcements group is stored)

Q: Slack has both 1-1 messages and group conversations. So what's the final sharding key?

2 possible approaches:

1. 2 separate database

1. Group conversation database - sharded by group id
2. 1-1 conversation database - sharded by user id

2. Treat 1-1 conversations as "ad-hoc" groups of 2 participants

1. "Sanjana => Hi => Tarun" is treated as a message in the group (sanjana_id, tarun_id) or conversation_id (if the conversation involves 2+ people)

Relational Database

You should only use it if you individual data items (1 row) is “small”: < 1kb, or a few kbs max. If your rows are usually > 10Kb, then you should probably not use a SQL database.

Note that your database will not complain even if you try to store 100MB row. It’s just stupid/bad-database-choice to store such large values in a SQL db row.

This does NOT mean that SQL can only handle 10kb of data. SQL can handle terabytes of data.. it’s just that the data must be in multiple rows and tables.. the individual rows should not be too large.

How Storage Works

1. Magnetic: How do Hard Disk Drives Work?  💻💿🛠 
2. Solid State: How do SSDs Work? | How does your Smartphone store data? |  Insanely Complex Nanoscopic Structures! 
3. RAM: How does Computer Memory Work? 💻🛠 

Sequential vs Random Access

The HDD might be spinning at 7200 RPM.

How much time will it take to complete 1 spin?

7200 rpm ⇒ 7200/60 rps ⇒ 120 rps

time to complete 1 rotation ⇒ 1 / (120) s = 8ms

How much time does it take to move the spindle (read head)?

~10ms

How much time to read the entire track (100 MB of sequential data)?

10ms to move the spindle to correct track

• 8 ms → to spin the disk once

bandwidth = 100MB / 18ms = 100MB / 0.018s = 5.5Gbps

How much time to read 4kb of random data?

Why 4kb? Because your disk is NOT byte addressable. Whenever you read/write, you always do it in chunks of 4kb.

Because random data will be on some different track

10ms to move the spindle to correct track

• 8 ms → to spin the disk once

bandwidth = 4kb / 18ms = 222kbps

Sequential access is up to 10,000x faster than random access!

True irrespective of the storage technology (HDD, SSD, RAM, L3 cache, Brain)